/*
https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/solution/ju-xing-qu-yu-bu-chao-guo-k-de-zui-da-sh-70q2/
 */
import java.util.TreeSet;

public class Solution363 {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int m=matrix.length;
        int n=matrix[0].length;
        int ans=Integer.MIN_VALUE;
        for (int i=0;i<m;i++){
            int[] sum=new int[n];
            for (int j=i;j<m;j++){
                for (int p=0;p<n;p++){
                    sum[p]=sum[p]+matrix[j][p];
                }
                int s=0;
                TreeSet<Integer> treeSet=new TreeSet<>();
                treeSet.add(0);
                for (int p=0;p<n;p++){
                    s=s+sum[p];
                    Integer integer=treeSet.ceiling(s-k);
                    if (integer!=null){
                        ans=Math.max(ans,s-integer);
                    }
                    treeSet.add(s);
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution363().maxSumSubmatrix(new int[][]{{1,0,1},{0,-2,3}},2));
    }
}
